package sjjg.sort;

public class merge_sort {
    private static int[] auxi;

    public static void main(String[] args) {
        int arr[] = {1, 3, 4, 2, 5};
        auxi = new int[arr.length];
        int low = 0;
        int height = arr.length - 1;
        System.out.println(mergeSort(arr, low, height));
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
    /*由mergeSort改写逆序对*/
     private static int mergeSort(int[] arr, int low, int height) {
        if (low == height) return 0;
        int mid = (height - low) / 2 + low;
        int s1 = mergeSort(arr, low, mid);
        int s2 = mergeSort(arr, mid + 1, height);

        int sum=s1+s2;
        int t = low;
        int p1 = low;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= height) {
            if (arr[p1] < arr[p2]) {
                sum++;
                auxi[t++] = arr[p1++];
            } else {
                auxi[t++] = arr[p2++];
            }
        }
        while (p1 <= mid) {
            auxi[t++] = arr[p1++];
        }
        while ((p2 <= height)) {
            auxi[t++] = arr[p2++];
        }
        for (int i = low; i <= height; i++) {
            arr[i] = auxi[i];
        }
        return sum;
    }
    /*由mergeSort改写求最小和*/
   /* private static int mergeSort(int[] arr, int low, int height) {
        if (low == height) return 0;
        int mid = (height - low) / 2 + low;
        int s1 = mergeSort(arr, low, mid);
        int s2 = mergeSort(arr, mid + 1, height);

        int sum = s1 + s2;
        int t = low;
        int p1 = low;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= height) {
            if (arr[p1] < arr[p2]) {
                sum = sum + arr[p1] * (height - p2 + 1);
                auxi[t++] = arr[p1++];
            } else {
                auxi[t++] = arr[p2++];
            }
        }
        while (p1 <= mid) {
            auxi[t++] = arr[p1++];
        }
        while ((p2 <= height)) {
            auxi[t++] = arr[p2++];
        }
        for (int i = low; i <= height; i++) {
            arr[i] = auxi[i];
        }
        return sum;
    }*/
    /*原始mergeSort*/
    /*public static int mergeSort(int []arr,int low,int height){//分而治之
        if(low>=height){//递归结束条件
            return 0;
        }
        //分为两个等组 分
        int mid=low+(height-low)/2;//mid进行划分
        int  s1= mergeSort(arr,low,mid);//递归调用
        int  s2=  mergeSort(arr,mid+1,height);//递归调用
        //将两个数组进行合并 治
        int t=low;
        int p1=low;
        int p2=mid+1;
        int sum=s1+s2;
        while (p1<=mid&&p2<=height){
            if(arr[p1]<arr[p2]){//倒序
                sum=sum+(height-p2+1)*arr[p1];
                auxi[t++]=arr[p1++];
            }else {
                auxi[t++]=arr[p2++];
            }
        }
        while (p1<=mid){
            auxi[t++]=arr[p1++];
        }
        while (p2<=height){
            auxi[t++]=arr[p2++];
        }
        //拷贝到原数组中
        for (int i = low; i <=height ; i++) {
            arr[i]=auxi[i];
        }
        return sum;
    }*/
}
